package leetbook.hash;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;

public class Solution381 {

    public static void main(String[] args) {

        RandomizedCollection rc = new RandomizedCollection();
        System.out.println(rc.insert(4));
        System.out.println(rc.insert(3));
        System.out.println(rc.insert(4));
        System.out.println(rc.insert(2));
        System.out.println(rc.insert(4));

        System.out.println(rc.remove(4));
        System.out.println(rc.remove(3));
        System.out.println(rc.remove(4));
        System.out.println(rc.remove(4));
//        System.out.println(rc.getRandom());
    }

}

class RandomizedCollection {

    HashMap<Integer, HashSet<Integer>> valToIdxs;
    ArrayList<Integer> vals;
    Random rand;

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        valToIdxs = new HashMap<>();
        vals = new ArrayList<>();
        rand = new Random();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {

        HashSet<Integer> idxs = valToIdxs.get(val);
        if(idxs==null){
            idxs = new HashSet<Integer>();
            vals.add(val);
            idxs.add(vals.size()-1);
            valToIdxs.put(val,idxs);
            return true;
        }else{
            boolean flag = (idxs.size()==0);
            vals.add(val);
            idxs.add(vals.size()-1);
            return flag;
        }
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {

        HashSet<Integer> valIdxSet = valToIdxs.get(val);  //val的所有下标
        if(valIdxSet==null||valIdxSet.size()==0) return false;
        int lastVal = vals.get(vals.size()-1); //vals列表的最后一个元素
        if(lastVal==val){
            vals.remove(vals.size()-1);
            valIdxSet.remove(vals.size());
            return true;
        }
        HashSet<Integer> lastvalIdxSet = valToIdxs.get(lastVal);  //vals列表的最后一个元素对应的所有下标
        //在vals中把要删除的元素val和最后一个元素lastVal替换
        int remInd = valIdxSet.iterator().next(); //从val的下标中选一个
        //替换
        vals.set(remInd,lastVal);
        lastvalIdxSet.add(remInd);
        //删除
        valIdxSet.remove(remInd);
        lastvalIdxSet.remove(vals.size()-1);
        vals.remove(vals.size()-1);
        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        return vals.get(rand.nextInt(vals.size()));
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */